{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python38564bitd6b24316ed9c45ef904db727e98f579f",
   "display_name": "Python 3.8.5 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. 寻找两个正序数组中的中位数  \n",
    "给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。  \n",
    "请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。  \n",
    "你可以假设 nums1 和 nums2 不会同时为空。  \n",
    "示例 1:  \n",
    "nums1 = [1, 3]  \n",
    "nums2 = [2]  \n",
    "则中位数是 2.0  \n",
    "示例 2:  \n",
    "nums1 = [1, 2]  \n",
    "nums2 = [3, 4]  \n",
    "则中位数是 (2 + 3)/2 = 2.5  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def findMedianSortedArrays(nums1, nums2):\n",
    "        def getK(k):\n",
    "            p1, p2 = 0, 0\n",
    "            while True:\n",
    "                if p1 == m:\n",
    "                    return nums2[p2 + k - 1]\n",
    "                if p2 == n:\n",
    "                    return nums1[p1 + k - 1]\n",
    "                if k == 1:\n",
    "                    return min(nums1[p1], nums2[p2])\n",
    "                new_p1 = min(p1 + k // 2 - 1, m - 1)\n",
    "                new_p2 = min(p2 + k // 2 - 1, n - 1)\n",
    "                nums1_p = nums1[new_p1]\n",
    "                nums2_p = nums2[new_p2]\n",
    "                if nums1_p <= nums2_p:\n",
    "                    k -= new_p1 - p1 + 1\n",
    "                    p1 = new_p1 + 1\n",
    "                else:\n",
    "                    k -= new_p2 - p2 + 1\n",
    "                    p2 = new_p2 + 1\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        total_length = m + n\n",
    "        return (getK((total_length + 1) // 2) + getK((total_length + 2) // 2)) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "1.5\n3.5\n"
    }
   ],
   "source": [
    "print(Solution.findMedianSortedArrays([1], [2]))\n",
    "print(Solution.findMedianSortedArrays([1, 4], [2, 3, 5, 6]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10. 正则表达式匹配  \n",
    "给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '\\*' 的正则表达式匹配。  \n",
    "'.' 匹配任意单个字符  \n",
    "'\\*' 匹配零个或多个前面的那一个元素  \n",
    "所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。  \n",
    "说明:  \n",
    "s 可能为空，且只包含从 a-z 的小写字母。  \n",
    "p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \\*。  \n",
    "示例 1:  \n",
    "输入:  \n",
    "s = \"aa\"  \n",
    "p = \"a\"  \n",
    "输出: false  \n",
    "解释: \"a\" 无法匹配 \"aa\" 整个字符串。  \n",
    "示例 2:  \n",
    "输入:  \n",
    "s = \"aa\"  \n",
    "p = \"a\\*\"  \n",
    "输出: true  \n",
    "解释: 因为 '\\*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 \"aa\" 可被视为 'a' 重复了一次。  \n",
    "示例 3:  \n",
    "输入:  \n",
    "s = \"ab\"  \n",
    "p = \".\\*\"  \n",
    "输出: true  \n",
    "解释: \".\\*\" 表示可匹配零个或多个（'\\*'）任意字符（'.'）。  \n",
    "示例 4:  \n",
    "输入:  \n",
    "s = \"aab\"  \n",
    "p = \"c\\*a\\*b\"  \n",
    "输出: true\n",
    "解释: 因为 '\\*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 \"aab\"。  \n",
    "示例 5:  \n",
    "输入:  \n",
    "s = \"mississippi\"  \n",
    "p = \"mis\\*is\\*p\\*.\"  \n",
    "输出: false  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isMatch(s, p):\n",
    "        # 递归\n",
    "        # if not p: return not s\n",
    "        # first = bool(s) and p[0] in {s[0], '.'}\n",
    "        # if len(p) >= 2 and p[1] == '*':\n",
    "        #     return self.isMatch(s, p[2:]) or first and self.isMatch(s[1:], p)\n",
    "        # else:\n",
    "        #     return first and self.isMatch(s[1:], p[1:])\n",
    "        # 动态规划\n",
    "        m, n = len(s), len(p)\n",
    "        memo = {}\n",
    "        def dp(i, j):\n",
    "            if ((i, j) in memo): return memo[(i, j)]\n",
    "            if (j == n): return i == m\n",
    "            pre = i < m and p[j] in {s[i], '.'}\n",
    "            if (j <= n - 2 and p[j + 1] == '*'):\n",
    "                tmp = dp(i, j + 2) or pre and dp(i + 1, j)\n",
    "            else:\n",
    "                tmp = pre and dp(i + 1, j)\n",
    "            memo[(i, j)] = tmp\n",
    "            return tmp\n",
    "        return dp(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "False\n"
    }
   ],
   "source": [
    "print(Solution.isMatch('aaa', 'b*'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}